package suanfa;

import com.alibaba.fastjson.JSONObject;

/**
 * 归并排序
 *  分解待排序的数组成两个各具 n/2 个元素的子数组，递归调用归并排序两个子数组，合并两个已排序的子数组成一个已排序的数组。
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {8,5,9,4,1};
        mergeSort(arr);
        System.out.println(JSONObject.toJSON(arr));
    }

    public static void mergeSort(int[] arr){
        int[] temp = new int[arr.length];
        internalMergeSort(arr, temp, 0, arr.length - 1);
    }

    private static void internalMergeSort(int[]arr , int[] temp,int left ,int right){
        // 当left == right时，不需要再划分
         if (left < right){
             int mid = (left+right)/2;
             internalMergeSort(arr, temp, left, mid);
             internalMergeSort(arr, temp, mid + 1, right);
             mergeSortedArray(arr, temp, left, mid, right);
         }
    }

    /**
     * 合并2个有序子序列
     * @param arr
     * @param temp
     * @param left
     * @param mid
     * @param right
     */
    public static void mergeSortedArray(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        // 把temp数据复制回原数组
        for (i = 0; i < k; i++) {
            arr[left + i] = temp[i];
        }
    }
}
